import java.util.Stack;

public class Test22 {
    public static boolean isPopOrder(int[] push,int[] pop){
        if (push == null || pop == null || push.length == 0 || pop.length == 0) return false;
        //存放入栈时的数据
        Stack<Integer> stack = new Stack<>();
        int pushIndex = 0; //入栈的指针
        int popIndex = 0; //出栈的指针
        while (popIndex < pop.length){
            // 入栈元素还未全部入栈的条件下，如果栈为空，或者栈顶的元素不与当前处理的相等，则一直进行栈操作，
            // 直到入栈元素全部入栈或者找到了一个与当出栈元素相等的元素
            while(pushIndex < push.length && (stack.isEmpty() || stack.peek() != pop[popIndex])){
                stack.push(push[pushIndex++]);
            }
            //入栈元素与出栈元素相同
            //出栈，出栈索引+1
            if(pop[popIndex] == stack.peek()){
                stack.pop();
                popIndex ++;
            }else { //如果没有找到相同的元素，而且入栈元素已经满了，返回false；
                return false;
            }
        }
        return true;
    }

    public static boolean isPopOrder2(int[] push,int[] pop){
        if (push == null || pop == null || push.length == 0 || pop.length == 0) return false;
        boolean flag = false; //标记
        Stack<Integer> pushStack = new Stack<>();//入栈

        // 记录下一个要处理的入栈元素的位置
        int nextPush = 0;
        // 记录下一个要处理的出栈元素的位置
        int nextPop = 0;
        while (nextPop < pop.length){
            while(pushStack.isEmpty() || pop[nextPop] != pushStack.peek()){
                if (nextPush >= push.length) break;//全部入栈,退出循环
                pushStack.push(push[nextPush++]);

            }
            if (pop[nextPop] == pushStack.peek()){
                pushStack.pop();
                nextPop ++;
            }else {
                break;
            }
        }
        //如果栈空了，说明符合条件
        if (pushStack.isEmpty()) flag = true;
        return flag;

    }

    public static void main(String[] args) {
        int[] push = {1, 2, 3, 4, 5};
        int[] pop1 = {4, 5, 3, 2, 1};
        int[] pop2 = {3, 5, 4, 2, 1};
        int[] pop3 = {4, 3, 5, 1, 2};
        int[] pop4 = {3, 5, 4, 1, 2};

        System.out.println(isPopOrder(push, pop1));
        System.out.println(isPopOrder(push, pop2));
        System.out.println(isPopOrder(push, pop3));
        System.out.println(isPopOrder(push, pop4));

        System.out.println();
        System.out.println(isPopOrder2(push, pop1));
        System.out.println(isPopOrder2(push, pop2));
        System.out.println(isPopOrder2(push, pop3));
        System.out.println(isPopOrder2(push, pop4));
        System.out.println(isPopOrder2(null, null));

    }
}
